#include "graph.h"
#include <queue>
using namespace std;
int d[10000];
int pi[10000];
struct Element
{
    int index;//索引
    Element(){}
    Element(int i)
    {
        this->index=i;
    }
    bool operator<(const Element& e) const
    {
        return d[index]>d[e.index];
    }
};

Graph::Graph(int V)
{
    //初始化点数
    this->V=V;
    //新建邻接链表保存各边
    this->adjList=new list<Edge>*[V];
    for(int i=0;i<V;i++)
    {
        adjList[i]=new list<Edge>;
    }
}

Graph::~Graph()
{
    for(int i=0;i<V;i++)
        delete adjList[i];
    delete []adjList;
}
void
Graph::addEdge(int start,int end,int weight)
{
    this->adjList[start]->push_back(Edge(start,end,weight));
}

void
Graph::printMap()
{
    for(int i=0;i<V;i++)
    {
        list<Edge>::iterator iter;
        for(iter=adjList[i]->begin();iter!=adjList[i]->end();iter++)
        {
            cout<<*iter<<"\t";
        }
        cout<<endl;
    }
}

void
Graph::init(int s)
{
    for(int i=0;i<V;i++)
    {
        d[i]=INF;
        pi[i]=NIL;   //初始化需要的两个数组
    }
    d[s]=0;     //设置源点距离为0
}

void
Graph::relax(int u,int v,int w)
{
    if(d[v]>d[u]+w)
    {
        d[v]=d[u]+w;
        pi[v]=u;
    }
}

void
Graph::dijkstra(int s)
{
    init(s);    //初始化操作
    priority_queue<Element> q;  //新建优先队列
    for(int i=0;i<V;i++)
    {
        q.push(Element(i)); //将节点加入队列
    }
    while(!q.empty())   //当队列不为空时进行
    {
        int u=q.top().index;
        q.pop();    //取出最小的点
        for(list<Edge>::iterator iter=adjList[u]->begin();iter!=adjList[u]->end();iter++)
        {
            //遍历u的所有边
            relax(u,iter->end,iter->length);    //松弛边
        }
    }
    //打印最短路信息
    for(int i=0;i<V;i++)
    {
        cout<<"点"<<i<<":"<<i;
        int temp=pi[i];
        while(temp!=NIL)
        {
            cout<<"<-"<<temp;
            temp=pi[temp];
        }
        cout<<"  距离为"<<d[i]<<endl;
    }
}

bool
Graph::bellmanFord(int s)
{
    init(s);    //初始化
    for(int i=0;i<V-1;i++)
    {
        for(int u=0;u<V;u++)
        {
            for(list<Edge>::iterator iter=adjList[u]->begin();iter!=adjList[u]->end();iter++)
            {   //遍历所有边
                relax(u,iter->end,iter->length);  //松弛操作
            }
        }
    }
    for(int u=0;u<V;u++)
    {
        for(list<Edge>::iterator iter=adjList[u]->begin();iter!=adjList[u]->end();iter++)
        {   //遍历所有边
            if(d[iter->end]>d[u]+iter->length)
                return false; 
        }
    }
    //打印最短路信息
    for(int i=0;i<V;i++)
    {
        cout<<"点"<<i<<":"<<i;
        int temp=pi[i];
        while(temp!=NIL)
        {
            cout<<"<-"<<temp;
            temp=pi[temp];
        }
        cout<<" 距离为"<<d[i]<<endl;
    }
    return true;
}
